package crazy;

public class MergeSort
{

	public static void main(String[] args)
	{
		DataWrap[] data = { new DataWrap(21, ""), new DataWrap(30, ""),
				new DataWrap(49, ""), new DataWrap(30, "*"),
				new DataWrap(16, ""), new DataWrap(9, "") };
		
		System.out.println("before sorting-->"+java.util.Arrays.toString(data));
		split(data, 0, data.length-1);
		System.out.println("after sorting-->"+java.util.Arrays.toString(data));
	}
	
	public static void split(DataWrap[] data, int left, int right)
	{
		if (left < right)
		{
			int center = (left+right)/2;
			split(data, left, center);
			split(data, center+1, right);
			mergeSort(data, left, center, right);//合并排序 
		}
	}
	
	public static void mergeSort(DataWrap[] data, int left, int center, int right)
	{
		DataWrap[] tmpArr = new DataWrap[data.length];
		int mid = center+1;
		int third = left;
		int tmp = left;
		
		while (left <= center && mid <= right)
		{
			if (data[left].compareTo(data[mid])<=0)
			{
				tmpArr[third++] = data[left++];
			} 
			else
			{
				tmpArr[third++] = data[mid++];
			}
			//left <= center && mid <= right-->[9, 16, 21, 30, 30*, null]
		}
		
		while (mid <= right)//把上面while循环中 溜掉的情况补上
		{
			tmpArr[third++] = data[mid++];
		}
		while (left <= center)//把上面while循环中 溜掉的情况补上
		{
			tmpArr[third++] = data[left++];
			//left <= center-->[9, 16, 21, 30, 30*, 49]
		}
		
		while (tmp <= right)//copy tmpArr[]'s data into data[]
		{
			data[tmp] = tmpArr[tmp++];
		}
	}

}

